package com.cuz.daileetcode;

public class Day46 {
    /****
     * 二丶最长的合法括号子串
     * 见DaiLeetCode46合法括号序列的最大深度，最长的合法括号子串
     * @param str
     * @return
     */
    public static int solution(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] charArray = str.toCharArray();
        int len = str.length();
        int[] dp = new int[len];
        int res = 0;
        //第一个位置结束无论是(还是) 必定是0
        for (int index = 1; index < len; index++) {
            //)结尾才能是合法的子串
            if (charArray[index] == ')') {
                //上一个可能于当前字符配对的括号
                int prePairMaybe = index - dp[index - 1] - 1;
                if (prePairMaybe >= 0 && charArray[prePairMaybe] == '(') {
                    //以当前字符结尾的合法子串 至少是这个长度
                    int curMaxLen = dp[index - 1] + 2;
                    //保证不越界 其实这里可以写 >0 因为dp[0]肯定是0
                    if (prePairMaybe - 1 >= 0) {
                        curMaxLen += dp[prePairMaybe - 1];
                    }
                    dp[index] = curMaxLen;
                }
            }
            res = Math.max(res, dp[index]);
        }
        return res;
    }
}
